package codingforgreat.class15;

import sun.security.provider.MD5;

import java.security.PublicKey;


// 如果i位置没有发生buy行为，说明有没有i位置都一样，那么buy[i] = buy[i-1]，这显而易见
// 如果i位置发生了buy行为, 那么buy[i] = sell[i - 2] - prices[i]，
// 因为你想在i位置买的话，你必须保证之前交易行为发生在0...i-2上，
// 因为如果i-1位置有可能参与交易的话，i位置就要cooldown了，
// 而且之前交易行为必须以sell结束，你才能buy，而且要保证之前交易尽可能得到最好的利润，
// 这正好是sell[i - 2]所代表的含义，并且根据buy[i]的定义，最后一定要 - prices[i]
//
// sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i])
// 如果i位置没有发生sell行为，那么sell[i] = sell[i-1]，这显而易见
// 如果i位置发生了sell行为，那么我们一定要找到 {之前获得尽可能好的收益 - 最后一次的收购价格尽可能低}，
// 而这正好是buy[i - 1]的含义！之前所有的"尽可能"中，最好的一个！
public class Class05_LC_309 {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int N  = prices.length;
        int[] buy = new int[N];
        int[] sell = new int[N];
        buy[0] = -prices[0];
        buy[1] = Math.max(-prices[0], -prices[1]);
        sell[1] = Math.max(0, prices[1] - prices[0]);
        for (int i = 2; i < N; i++) {
            buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        }
        return sell[N - 1];
    }

}
